import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class threeSum {
    /**
     * 三数之和
     * @author ShakeJ
     * @date 2024/3/18
     */
    /**
     * 给一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]
     * 此时满足i!=j j!=k等，同时还满足值之和为：nums[i]+nums[j]+nums[k]==0
     *
     */
    public static List<List<Integer>> method(int[] nums){
        List<List<Integer>> res=new ArrayList<>(); //返回的结果格式为二维链表
        int len = nums.length;
        if(nums==null ||  len<3){
            return res;
        }
        // 排序
        Arrays.sort(nums);
        // 遍历
        for(int i=0;i<len;i++){
            if(nums[i]>0){
                break;
            }
            // 对第一层循环去重
            if(i>0 && nums[i]==nums[i-1]){
                continue; // 跳过继续遍历
            }
            // 后续元素部分进行遍历
            int l = i + 1;
            int r = len - 1;
            while(l<r){
                // 三数之和
                int sum=nums[i]+nums[l]+nums[r];
                // 如果是0， 结果对应索引位置的值加入到结果集中
                if(sum==0){
                    res.add(Arrays.asList(nums[i], nums[l],nums[r]));
                    // 去重
                    while(l>0 && nums[l]==nums[l+1]){
                        l++;
                    }
                    while(r>0 && nums[r]== nums[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }else if(sum>0){
                    r--;
                }else if(sum<0){
                    l++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[]nums = {2,5,3,1,-1,-3,5,-5,6,-6};
        System.out.println(method(nums));
    }
}
